\chapter{Производящие функции - наше се и еще кое-что}

Лекция от 6 октября 2011 года

\section{О пользе представлений}
Итак, мы наконец дошли до, пожалуй, самой интересной части курса.

\begin{Def}
Пусть имеется числовая последовательность $a_0, a_1, a_2, a_3, ...$. Формальный степенной ряд $f\left(x\right) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n + ...$ называется нормальной производящей функцией, а формальный степенной ряд $F\left(x\right) = a_0 + a_1 \frac{x}{1!} + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + ... + a_n \frac{x^n}{n!} + ...$ - экспоненциальная производящая степенная функция.
\end{Def}

\paragraph{Примечание.} Формальный степенной ряд в данном случае обозначет, что производящая функция есть просто форма записи числовой последовательности, а не степенной ряд, но чуть позже мы введем ряд операций над производящими функциями и увидим, что у производящих функций много общего с теми самыми степенными рядами из матана.

\begin{Def}
Суммой двух обыкноенных производящих функций $f\left(x\right) = a_0 + a_1 x + ...$ и $g\left(x\right) = b_0 + b_1 x + ...$ называется обыкновенная производящая функция $h\left(x\right) = c_0 + c_1 x + ...$, причем $c_i = a_i + b_i$

Сумма двух экспоненциальных производящих функций $F\left(x\right) = a_0 + a_1 \frac{x}{1!} + ...$ и $G\left(x\right) = b_0 + b_1 \frac{x}{1!} + ...$ называется производящая функция $H\left(x\right) = c_0 + c_1 \frac{x}{1!} + ...$, причем $c_i = a_i + b_i$
\end{Def}

\begin{Def}
Пусть $f\left(x\right) = a_0 + a_1 x + ... $ и $g\left(x\right) = b_0 + b_1 x + ...$ - обыкновенные производящие функции, тогда произведением таких функций является обыкновенная производящая функция $h\left(x\right) = c_0 + c_1 x + ...$, причем $c_n = \sum_{i=0}^n a_i b_{n-i}$

Пусть $F\left(x\right) = a_0 + a_1 \frac{x}{1!} + ...$ и $G\left(x\right) = b_0 + b_1 \frac{x}{1!} + ...$ - экспоненциальные производящие функции, тогда их произведение - это экспоненциальная производящая функция $H\left(x\right) = c_0 + c_1 \frac{x}{1!} + ...$, причем $c_n = \sum_{i=0}^n \binom{n}{i}a_i b_{n-i}$
\end{Def}

Есть еще одна операция, котороя врядли окажется полезной, но для справки приведем и ее:

\begin{Def}
Произведением Адомара двух обыкновенных производящих функций $f\left(x\right) = a_0 + a_1 x + ...$ и $g\left(x\right) = b_0 + b_1 x + ...$ называется обыкновенная производящая функция $h\left(x\right) = c_0 + c_1 x + ...$, причем $c_i = a_i b_i$
\end{Def}

Касательно рассмотренных операций стоит сказать, что они ассоциативны, транзитины и дистрибутивна одна относительно другой. Теперь рассмотрим и некоторые особенные чсиловые последовательности.

Во-первых, нейтральным элементом по сложению для обыкновенных и экспоненциальных производящих функций является нулевая последовательность (ну вы это и так поняли).

Во-вторых, нейтральным элементом по умножению для обыкновенных производящих функций является единичная последовательность (опять же не трудно).

В-третьих, нейтральный элемент по произведению для экспоненциальных производящих функций - последовательность $1, 0, 0, 0 ,... $ (это не трудно проверить).

Наконец очевидно, что для операции сложения существует обратный элемент.

Далее чуть сложнее... По умножению для обыкновенных производящих функций существует обратный элемент в том и только в том случае, если $a_0 \not= 0$

Далее пусть имеется обыкновенная производящая функция $\sum_{n=0}^{+\infty} \alpha^n x^n$, умножим ее на выражение $1 - \alpha x$, получаем опять производящую функцию $c_0 + c_1 x + c_2 x^2 + ...$, рассмотрим, чему же равны числа $c_i$:
\[
	\begin{split}
		& c_0 = 1 \\
		& c_1 = \alpha - \alpha = 0
		& c_2 = \alpha^2 - \alpha \alpha^1 = 0
		& ... \\
		& c_n = \alpha^n - \alpha \alpha^{n-1} = 0
	\end{split}
\]
т. е. получили справа просто единицу, а тогда (неформально) можно получить:
\[
	\sum_{n=0}^{+\infty} \alpha^n x^n = \frac{1}{1-\alpha x}
\]
похожее соотношение было известно из матана, для бесконечноубывающей геометрической прогрессии, т. е. в случае $\left|x\right| < \frac{1}{\alpha}$. И на самом деле это не единственное сходство.

\paragraph{Пример.}
Рассмотрим следующее произведение:
\[
	\left(\sum_{n=0}^{+\infty} \left(1\right) \frac{x^n}{n!}\right)\left(\sum_{k=0}^{+\infty} {\left(-1\right)}^k \frac{x^k}{k!}\right) = \sum_{n=0}^{+\infty} \left(\sum_{i=0}^{n} \binom{n}{i} 1 \left(1\right) \left(-1\right)^{n-i}\right) x^n
\]
оно преобразовано по определению операции произведения экспоненциальных степенных рядов, но теперь представим, что мы перемножаем не формальные степенные ряды, а числовые ряды, тогда левая скобка эквивалентна $e^x$, а правая $e^{-x}$, а их произведение равно $e^x e^{-x} = 1$, а единицу можно представить следующим образом
\[
	\sum_{i=0}^{n} \left(-1\right)^{n-i} \binom{n}{i} =
	\begin{cases}
		1, & n = 0 \\
		0, & n > 0
	\end{cases}
\]
(Знакоперемнная сумма биномиальных коэффициентов равно 0), как видно получили одно и то же выражение с разных сторон.

\paragraph{Пример.}
Мы уже знаем $\sum_{n=0}^{+\infty} \alpha^n x^n = \frac{1}{1 - \alpha x}$, примем $\alpha = 1$, тогда получаем $\sum_{n=0}^{+\infty} x^n = \frac{1}{1 - x}$, т. е. можем сказать, что $\frac{1}{1 - x}$ производящая функция для единичной последовательности $1, 1, 1, ...$

\paragraph{Пример.}
Пусть $f\left(x\right)$ - обыкновенная производящая функция, тогда $f\left(x\right) \frac{1}{1-x}$ - последовательность частичных сумм последовательности $f\left(x\right)$.

Очевидно, что ${\left(1+n\right)}^n$ - производящая функция для ряда биномиальных коэффициентов $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, ...$ для любых $r$ (в том числе и комплексных).

\paragraph{Пример.}
Пусть у нас есть две производящие функции:
\[
	\begin{split}
		& {\left(1 + x\right)}^n = \sum_{i=0}^{n} \binom{n}{i} x^i \\
		& {\left(1 + x\right)}^m = \sum_{j=0}^{m} \binom{m}{j} x^j
	\end{split}
\]
Перемножим их как обычные степенные ряды:
\[
	{\left(1+x\right)}^n {\left(1+x\right)}^m = {\left(1+x\right)}^{n+m} = \sum_{k=0}^{n+m} \binom{n+m}{k} x^k
\]
А теперь рассмотрим их как формальные степенные ряды:
\[
	\left(1+x\right)^n \left(1+x\right)^m = \sum_{k=0}^{n+m} x^k \sum_{i=0}^k \binom{n}{i} \binom{m}{k-i}
\]
Далее приравниваем внутренние суммы и получаем известное нам выражение (но проще):
\[
	\binom{n+m}{k} = \sum_{i=0}^k \binom{n}{i} \binom{m}{k-i}
\]

\paragraph{Пример.}
\[
	{\left(1+x\right)}^n = \sum_{k=0}^n \binom{n}{k} x^k = \sum_{k=0}^n \frac{{\left(n\right)}_k}{k!} x^k
\]
т. е. получили экспоненциальную произодящую функцию для $\left(n\right)_k$

\section{Рекуррентные соотношения}

Ну тут краткое вступительное слов - здрасте). Ну теперь перейдем к рекурсии, а точнее к решению рекуррентных соотношений. Решением рекуррентного соотношения яляется замкнутое выражение для последовательности чисел, которые представляются соотношением.

\begin{Def}
Пусть $a_0, a_1, a_2, ....$ - числовая последовательность, такая что для любого $\forall n \ge m > 0$, $a_{n+m} = f\left(a_{n+m-1}, a_{n+m-2}, a_{n+m-3}, ... , a_{n}\right)$, тогда последовательность называется рекуррентной, а выражение рекуррентным выражением для числовой последовательности.
\end{Def}

\begin{Def}
Линейным рекуррентным соотношением $m$-ого порядка называется рекуррентное соотношение вида:
\[
	a_{n+m} = b_1 \left(n\right) a_{n+m-1} + b_2 \left(n\right) a_{n+m-2} + ... + b_{m} \left(n\right) a_{m} + u\left(n\right)
\]

Если $u\left(n\right) \equiv 0$, то рекуррентное соотношение называется однородным.

Если $b_i \left(n\right) \equiv const$, то соотношение называется соотношением с постоянными коэффициентами.
\end{Def}

\paragraph{Пример.}
Решим простое рекуррентное соотношение:
\[
	a_{n+1} = b a_n
\]
это не трудно решить, решение очевидно $a_n = a_0 b^n$. Предположим, что и для любого другого линейного рекуррентного соотношения решение также является полиномом, тогда рассмотрим:
\[
	a_{n+2} = b_1 a_{n+1} + b_2 a_{n}
\]
ищем решение в виде $a_n = r^n$, тогда подставив получим уравнение:
\[
	r^2 - b_1 r - b_2 = 0
\]
это называется характеристическим уравнением, оно имеет 3 различных варианта решения:
\[
	\begin{split}
	& r_1 \not= r_2 \in \mathbb{R} \\
	& r_1, r_2 \in \mathbb{C} \\
	& r_1 = r_2 \in \mathbb{R}
	\end{split}
\]

В первом случае общее решение рекуррентного соотношения имеет следующий вид:
\[
	a_n = c_1 r_1^n + c_2 r_2^n
\]
покажем на примере, что это действительно так, рассмотрим последовательность чисел Фибоначчи:
\[
	\begin{split}
	& F_{n+2} = F_{n+1} + F_n \\
	& F_0 = 0 \\
	& F_1 = 1
	\end{split}
\]
Характеристическое уравнение для данного рекурентного соотношения выглядит так:
\[
	\begin{split}
		& r^2 - r - 1 = 0 \\
		& r_{1,2} = \frac{1 \pm \sqrt{5}}{2}
	\end{split}
\]
Далее нужно определить значения констант по начальным условиям:
\[
	\begin{split}
		& 0 = c_1 + c_2 \\
		& 1 = c_1 \frac{1 + \sqrt{5}}{2} + c_2 \frac{1-\sqrt{5}}{2}
	\end{split}
\]
Решение:
\[
	F_n = \frac{1}{\sqrt{5}} {\left(\frac{1+\sqrt{5}}{2}\right)}^n - \frac{1}{\sqrt{5}} {\left(\frac{1-\sqrt{5}}{2}\right)}^n
\]

Заметна аналгогия с дифференциальными уравнениями. На самом деле, решения линейного рекуррентного соотношения образуют линейное пространство, тогда для рекуррентного соотношения вида $a_{n+2} = b_1 a_{n+1} + b_2 a_n$, как мы уже сказали возможны три вида решений (первый случай мы уже рассмотрели). Фундаментальная система для кратных корней будет иметь вид: $\{nr^n; r^n\}$, случай двух комплексных корней это обобщение первого случая.

\paragraph{Пример.}
Рассмотрим забавное соотношение $a_{n+2} = 2 a_{n+1} - a_n$, его характеристическое уравнение принимает вид ${\left(r+1\right)}^2 = 0$ и имеет кратный корень $-1$ кратности 2, тогда решением (для простоты частным) является выражение $a_n = n {\left(-1\right)}^n + {\left(-1\right)}^n$, проверим это:
\[
	\left(n+2\right) {\left(-1\right)}^{n+2} + {\left(-1\right)}^{n+2} = n {\left(-1\right)}^n + 3 {\left(-1\right)}^n
\]
Теперь подставим проверяемое решение в правую часть:
\[
	-2 \left(\left(n+1\right) {\left(-1\right)}^{n+1} + {\left(-1\right)}^{n+1}\right) - \left(n {\left(-1\right)}^n + {\left(-1\right)}^n\right) = n {\left(-1\right)}^{n} + 3 {\left(-1\right)}^n
\]

\subsection{Рекурсия и производящие функции}

Мы рассмотрели достаточно простой способ решения рекуррентных соотношений, но к сожалению такой способ имеет ряд ограничений на вид соотношений (например решать неоднородные рекуррентные соотношения им уже достаточно тяжело), как же быть? А все очень просто, все  комбинаторике решается через производящие функции, просто пока не известно как)

Рассмотрим простой пример
\[
	\begin{split}
		& a_{n+1} = 4 a_n - 100 \\
		& a_0 = 50
	\end{split}
\]
Уравнение не очень сложное, но оно не однородное, и это печально... Поступим следующим образом, домножим левую и правую часть на $x^{n+1}$ и просуммируем по всем $n$:
\[
	\begin{split}
		& x^{n+1} a_{n+1} = 4 x^{n+1} a_n - 100 x^{n+1} \Leftrightarrow \\
		& \Leftrightarrow \sum_{n=0}^{\infty} x^{n+1} a_{n+1} = 4 \sum_{n=0}^{\infty} x^{n+1} a_n - 100 \sum_{n=0}^{\infty} x^{n+1}
	\end{split}
\]
Получили что-то очень похожее на обыкновенные производящие функции, попробуем докурить это, пусть
\[
	f\left(x\right) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
\]
тогда
\[
	\begin{split}
		& f\left(x\right) - a_0 = 4 x f\left(x\right) - \frac{100 x}{1 - x} \Leftrightarrow \\
		& \Leftrightarrow f\left(x\right) = \frac{a_0}{1 - 4 x} - \frac{100 x}{\left(1 - x\right)\left(1 - 4 x\right)}
	\end{split}
\]
Теперь разложим второе логаемое на простейшие:
\[
	\begin{split}
		& \frac{x}{\left(1 - x\right)\left(1 - 4 x\right)} = \frac{A}{1 - x} + \frac{B}{1 - 4 x} \Leftrightarrow \\
		& \Leftrightarrow A + B = 0, -4 A - B = 1 \\
		& A = -\frac{1}{3}, B = \frac{1}{3}
	\end{split}
\]
Соберем теперь все вместе:
\[
	\sum_{n=0}^{\infty} a_n x^n = a_0 \sum_{n=0}^{\infty} 4^n x^n - \frac{100}{3} \sum_{n=0}^{\infty} 4^n x^n + \frac{100}{3} \sum_{n=0}^{\infty} x^n
\]
откуда получаем:
\[
	a_n = a_0 4^n - \frac{100}{3} \left[4^n - 1\right]
\]

В целом все достаточно понятно, за исключением одного момента, как догадаться, что домножать нужно на $x^{n+1}$? Ну тут все достаточно просто, для начала удобно привести рекуррентное соотношение к форме:
\[
	b_0 a_{n+m} + b_1 a_{n+m-1} + b_2 a_{n+m-2} + ... + b_m a_{n} = 0
\]
в этом случае как правило требуется домножать на $x^{n+m}$, если таким образом мы не получили ничего приятного, то подправляем степень, чтобы после суммирования по всем $n$ свернуть суммые в уравнение на производящих функциях.

\subsection{Рекурсия с переменными коэффициентами}

\begin{Def}
Пусть у нас имеется обыкновенная производящая функция:
\[
	f\left(x\right) = a_0 + a_1 x + a_2 x^2 + ...
\]
тогда производной этой производящей фукции называется производящая функция:
\[
	f'\left(x\right) = a_1 + 2 a_2 x + 3 a_3 x^3 + ...
\]
\end{Def}

\begin{Def}
Пусть у нас имеется обыкновенная производящая функция:
\[
	f\left(x\right) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
\]
тогда интегралом этой производящей функции называется производящая функция:
\[
	\int f\left(x\right) = a_0 x + \frac{a_1}{2} x^2 + \frac{a_2}{3} x^3 + ...
\]
\end{Def}

Рассмотрим забавную задачу, построить рекуррентное соотношение для последовательности:
\[
	\begin{split}
		& a_n = \binom{2n}{n} \\
		& a_0 = 1
	\end{split}
\]
\[
	\begin{split}
		& a_{n+1} = \binom{2\left(n+1\right)}{n+1} = \frac{{\left(2 n + 2\right)}_{n + 1}}{\left(n + 1\right)!} = \\
		& = \frac{\left(2 n + 2\right)\left(2 n + 1\right) 2 n \left(2 n - 1\right)...\left(n + 2\right)}{\left(n+1\right)!} = \\
		& = \frac{2 \left(n+1\right)\left(2 n + 1\right) 2 n \left(2 n - 1\right) ... \left(n + 2\right)}{\left(n+1\right)!} = \\
		& = \frac{2 \left(2 n + 1\right) 2 n \left(2 n - 1\right) ... \left(n + 2\right)\left(n + 1\right)}{\left(n+1\right) n!} = 
		& = \frac{2 \left(2n+1\right)}{n+1} \binom{2n}{n}
	\end{split}
\]
и легким движением руки мы получаем:
\[
	\left(n+1\right) a_{n+1} = 2 \left(2 n + 1\right) a_n
\]
 А теперь сделаем глупость, и решим уравнение, которые сами только что получили, т. е. стараемся найти обыкноенную производящую функцию вида:
\[
	f\left(x\right) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
\]
Теперь сразу заметим, что если мы домножим все на $x^n$, а не на $x^{n+1}$, то слева получаем производную обыкновенной производящей функции, так и поступим:
\[
	\begin{split}
		& \sum_{n=0}^{\infty} \left(n+1\right) a_{n+1} x^n = 4 \sum_{n=0}^{\infty} n a_n x^n + 2 \sum_{n=0}^{\infty} a_n x^n \Leftrightarrow \\
		& \Leftrightarrow f'\left(x\right) = 4 x f'\left(x\right) + 2 f\left(x\right) \Leftrightarrow \\
		& \Leftrightarrow \frac{2}{1 - 4 x} = \frac{f'\left(x\right)}{f \left(x\right)}
	\end{split}
\]
а теперь решаем полученный "диффур":
\[
	\begin{split}
		& \frac{2 dx}{1 - 4 x} = \frac{d f}{f} = \Leftrightarrow d \ln f = -\frac{1}{2} \frac{d \left(1 - 4 x\right)}{1 - 4 x} = \\
		& = -\frac{1}{2} d \ln \left(1 - 4 x\right) = d \frac{1}{\sqrt{1 - 4 x}} \Leftrightarrow \\
		& f = \frac{1}{\sqrt{1 - 4 x}}
	\end{split}
\]
Далее хитропользуем бином Ньютона:
\[
	\begin{split}
		& \left(1 - 4 x\right)^{-\frac{1}{2}} \sum_{n=0}^{\infty} \binom{-\frac{1}{2}}{n} x^n \left(-4\right)^n = \\
		& = 1 + \sum_{n=1}^{\infty} \frac{\left(-\frac{1}{2}\right)\left(-\frac{1}{2} - 1\right) ... \left(-\frac{1}{2} - n + 1\right)}{n!} \left(-4\right)^n x^n = \\
		& = 1 + \sum_{n=1}^{\infty} \frac{\frac{1}{2} \frac{3}{2} \frac{5}{2} ... \left(n - \frac{1}{2}\right)}{n!} \left(-4\right)^n \left(-1\right)^n x^n = \\
		& =  1 + \sum_{n=1}^{\infty} \frac{1\cdot3 \cdot5 \cdot 7 \cdot ... \cdot \left(2 n - 1\right)}{n!} 2^n x^n = \\
		& = 1 + \sum_{n=1}^{\infty} \frac{1 \cdot 1 \cdot 2 \cdot 3 \cdot 2 \cdot 2 \cdot 5 \cdot 3 \cdot 2 \cdot ... \left(2 n - 1\right) \cdot n \cdot 2}{n! \cdot n!} x^n = \\
		& =  1 + \sum_{n=1}^{\infty} \binom{2n}{n} x^n = \sum_{n=0}^{\infty} \binom{2n}{n} x^n
	\end{split}
\]

Рассмотрим другой пример, возьмем совершенно неизвестную рекуррентную последовательность:
\[
	\begin{split}
		& a_{n+1} = \left(n+1\right) a_n \\
		& a_0 = 1
	\end{split}
\]
к сожалению решить такое уравнение с помощью обыкновенных производящих функций не так то просто (не уверен, что вообще возможно), дело в том аналогии с методами математического анализа для полученного дифференциального уравнения не совсем подходят, но в нашем случае все достаточно просто решается путем следующего эмпирического предположения:

все в комбинаторике решается путем производящих функций, если нам не помогают обыкновенные производящие функции, то помогут экспоненциальные, проверим...

\[
	F\left(x\right) = a_0 + a_1 x + \frac{a_2}{2} x^2 + \frac{a_3}{3!} x^3 + ...
\]
Домножаем все рекуррентное соотношение на $\frac{x^{n+1}}{\left(n+1\right)}$ и суммируем по всем $n$:
\[
	\sum_{n=0}^{\infty} a_{n+1} \frac{x^{n+1}}{\left(n+1\right)!} = \sum_{n=0}^{\infty} a_n \left(n+1\right) \frac{x^{n+1}}{\left(n+1\right)!} = x \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}
\]
(* на самом деле такое красивое сокращение получается не всегда, ну да и ладно, это далеко не главная проблема в решении))
\[
	\begin{split}
		& F\left(x\right) = \frac{a_0}{1 - x} \\
		& F\left(x\right) = a_0 \sum_{n=0}^{\infty} n! \frac{x^n}{n!}
	\end{split}
\]
(* вот блин неожиданность получили факториал...)
